package com.unbiz.common.collection;


import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collections;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Set;
import java.util.function.Function;

import com.unbiz.common.Emptys;

/**
 * 使用String作为key,int作为value index的hash表。
 * 使用putIndex时，不能重复插入相同的key，后面插入的的忽略
 * 一般存储索引数据
 * 
 * @author <a href="mailto:xuchen06@baidu.com">xuc</a>
 * @version create on 2014年9月15日 上午5:20:20
 */
public class StringHashMap<T> extends AbstractMap<String, T>{
    /** 默认的初始容量 - <code>2的整数次幂</code>. */
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    /** 最大容量 - <code>2的整数次幂</code>. */
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    /** 默认的负载系数 */
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 私有变量
    private ArrayList<T> values = null;
    private Entry[] table;
    private int count;
    private int threshold;
    private float loadFactor;

    /** 创建一个hash表，使用默认的初始容量<code>16</code>和默认的负载系数<code>0.75</code>。 */
    public StringHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 创建一个hash表，使用指定的初始容量和默认的负载系数<code>0.75</code>。
     * 
     * @param initialCapacity hash表的初始容量
     * @throws IllegalArgumentException 如果初始容量小于或等于<code>0</code>
     */
    public StringHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 创建一个hash表，使用默认的指定的初始容量和指定的负载系数。
     * 
     * @param initialCapacity hash表的初始容量
     * @param loadFactor 负载系数
     * @throws IllegalArgumentException 如果初始容量小于或等于<code>0</code>，或负载系数不是正数
     */
    @SuppressWarnings("unchecked")
    public StringHashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }

        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        }

        if (loadFactor <= 0) {
            throw new IllegalArgumentException("Illegal Load: " + loadFactor);
        }

        // 确保初始容量为2的整数次幂.
        int capacity = 1;

        while (capacity < initialCapacity) {
            capacity <<= 1;
        }

        this.loadFactor = loadFactor;
        table = new Entry[capacity];
        threshold = (int) (capacity * loadFactor);
    }

    /**
     * 取得当前hash表中元素的个数。
     * 
     * @return 元素个数
     */
    public int size() {
        return count;
    }

    /**
     * 测试hash表是否为空。
     * 
     * @return 如果为空，则返回<code>true</code>
     */
    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * 查看hash表中是否存在指定的key。
     * 
     * @param key 要搜索的key
     * @return 如果找到，则返回<code>true</code>
     */
    public boolean containsKey(String key) {
        Entry[] tab = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;

        for (Entry e = tab[index]; e != null; e = e.next) {
            if (e.hashCode() == hash && key.equals(e.key)) {
                return true;
            }
        }

        return false;
    }

    /**
     * 查看hash表中是否存在指定的值。
     * 
     * @param value 要搜索的值
     * @return 如果找到，则返回<code>true</code>
     */
    public boolean containsValue(Object value) {
    	if(values==null) return false;

        boolean valueIsNull = value == null;

        for (int i = values.size(); i-- > 0;) {
        	T e = values.get(i);
        	if (valueIsNull ? e == null : e!=null && value.equals(e)) {
                return true;
            }
        }

        return false;
    }   
  


	@Override
	public Set<java.util.Map.Entry<String, T>> entrySet() {
		// TODO Auto-generated method stub
		return new EntrySet();
	}
    /**
     * 查看hash表中是否存在指定的Index值。
     * 
     * @param value 要搜索的值
     * @return 如果找到，则返回<code>true</code>
     */
    public boolean containsIndex(int value) {
        Entry[] tab = table;
        boolean valueIsNull = value == 0;
        for (int i = tab.length; i-- > 0;) {
            for (Entry e = tab[i]; e != null; e = e.next) {
                if (valueIsNull ? e.value == 0 : value==e.value) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 从hash表中取得和指定key对应的值。
     * 
     * @param key 要查找的key
     * @return key所对应的值，如果没找到，则返回<code>0</code>
     */
    public int getIndex(String key) {
        Entry[] tab = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;

        for (Entry e = tab[index]; e != null; e = e.next) {
            if (e.hashCode() == hash && key.equals(e.key)) {
                return e.value;
            }
        }       
        return 0;
    }
    
    public T getValue(int index) {    	
        return this.values.get(index);
    }
    
    
    public T setValue(int index,T value) {    	
        return this.values.set(index,value);
    }
    
    /**
     * 从hash表中取得和指定key对应的值。
     * 
     * @param key 要查找的key
     * @return key所对应的值，如果没找到，则返回<code>values[0]</code>
     */
    public T get(String key) {    	
    	int index = this.getIndex(key);
    	if(this.values==null) return null;
        return this.values.get(index);
    }

    public T computeIfAbsent(String key,
            Function<? super String, ? extends T> mappingFunction) {
        Objects.requireNonNull(mappingFunction);
        T v;
        if ((v = get(key)) == null) {
            T newValue;
            if ((newValue = mappingFunction.apply(key)) != null) {
                put(key, newValue);
                return newValue;
            }
        }

        return v;
    }
    
    /**
     * 将key和指定对象的index相关联，并保存在hash表中。不能重复插入
     * 
     * @param key 对象的key
     * @param value 对象的index
     * @return 如果指定key已经存在，则不做任何操作，返回key所对应的原先的值
     * 		成功插入，返回0.
     */
    public int putIndex(String key, int value) {
    	if(value<=0){
    		throw new IndexOutOfBoundsException();
    	}
        // Makes sure the key is not already in the hashtable.
        Entry[] tab = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;

        for (Entry e = tab[index]; e != null; e = e.next) {
            if (e.hashCode() == hash && key.equals(e.key)) {
                int old = e.value;
                if(old!=0){
               //- e.value = value;
                	return old;
                }
                else{
                	count++;
                	e.value = value;
                	return 0;
                }
            }
        }

        if (count >= threshold) {
            rehash();

            tab = table;
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        Entry e = new Entry(key, value, tab[index]);

        tab[index] = e;
        count++;
        return 0;
    }


    /**
     * 将key和指定对象相关联，并保存在hash表中。
     * 
     * @param key 对象的key
     * @param value 对象（值）
     * @return 如果指定key已经存在，则返回key所对应的index的值
     */
    @Override
    public T put(String key, T value) {
    	if(this.values==null){
    		values = new ArrayList<T>(table.length);
    		values.add(null);
    	}
    	int index = this.values.size();        
        int index2 = putIndex(key,index);
        if(index2==0){
        	this.values.add(value);
        	return null;
        }
        else{
        	T old = this.values.get(index2);
        	this.values.set(index2,value);
        	return old;
        }
        
    }
    
    /**
     * 如果value 和原来的值相等，则更新
     * @param key
     * @param index
     * @param value
     * @return
     */
    public boolean putIfEquals(String key,T value, T org) {
    	if(this.values==null){
    		values = new ArrayList<T>(table.length);
    		values.add(null);
    	}
    	int index = this.values.size();        
        int index2 = putIndex(key,index);
        if(index2==0){
        	this.values.add(value);
        	return true;
        }
        else{
        	T old = this.values.get(index2);
        	if(old!=null && org.equals(old)){
        		this.values.set(index2,value);
        		return true;
        	}
        	return false;
        }
        
    }
    

    /**
     * 将key和指定对象和index相关联，并保存在hash表中。
     * 
     * @param key 对象的key
     * @param value 对象（值）
     * @return 如果指定key已经存在，则返回key所对应的原先的值
     */
    public T put(String key, int index, T value) {
    	if(index<=0){
    		throw new IndexOutOfBoundsException();
    	}
    	if(this.values==null){
    		values = new ArrayList<T>(table.length);
    		values.add(null);
    	}    	      
        int index2 = putIndex(key,index);
        if(index2==0){
        	while(index>=values.size())
        		values.add(null);	
    		
        	values.set(index,value);		
        	return null;
        }
        else{
        	T old = this.values.get(index2);
        	while(index>=values.size())
        		values.add(null);
        	values.set(index,value);	
        	return old;
        }
        
    }
    
    /**
     * 从hash表中删除一个值。
     * 
     * @param key 要删除的值所对应的key
     * @return 如果指定key已经存在，则返回key所对应的原先的值的index
     */
    public int remove(String key) {
        Entry[] tab = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;

        for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
            if (e.hashCode() == hash && key.equals(e.key)) {
                if (prev != null) {
                    prev.next = e.next;
                } else {
                    tab[index] = e.next;
                }

                count--;

                int oldValue = e.value;

                e.value = 0;
                return oldValue;
            }
        }

        return 0;
    }

    /** 清除hash表。 */
    public void clear() {
        Entry[] tab = table;

        for (int index = tab.length; --index >= 0;) {
            tab[index] = null;
        }

        count = 0;
        if(values!=null){
        	values.clear();
        }
    }

    public String[] keys() {
        if (count == 0) {
            return Emptys.EMPTY_STRING_ARRAY;
        }

        String[] keys = new String[count];
        int index = 0;

        for (Entry element : table) {
            Entry entry = element;

            while (entry != null) {
                keys[index++] = entry.key;
                entry = entry.next;
            }
        }

        return keys;
    }    

    public List<T> values(){
    	return values;
    }    

    /**
     * 取得字符串表示。
     * 
     * @return 字符串表示
     */
    @Override
    public String toString() {
        StringBuilder buffer = new StringBuilder();

        buffer.append('{');

        String[] keys = keys();

        for (int i = 0; i < keys.length; i++) {
        	String key = keys[i];
            int value = getIndex(key);

            if (i > 0) {
                buffer.append(", ");
            }

            buffer.append(key).append('=').append(value);
        }

        buffer.append('}');

        return buffer.toString();
    }

    /** 重构hash表，倍增其容量。 */
    protected void rehash() {
        int oldCapacity = table.length;
        Entry[] oldMap = table;

        int newCapacity = oldCapacity * 2;

        @SuppressWarnings("unchecked")
        Entry[] newMap = new Entry[newCapacity];

        threshold = (int) (newCapacity * loadFactor);
        table = newMap;

        for (int i = oldCapacity; i-- > 0;) {
            for (Entry old = oldMap[i]; old != null;) {
                Entry e = old;

                old = old.next;

                int index = (e.hashCode() & 0x7FFFFFFF) % newCapacity;

                e.next = newMap[index];
                newMap[index] = e;
            }
        }
    }

    /**
     * 取得hash表的容量。
     * 
     * @return hash表的容量
     */
    protected int getCapacity() {
        return table.length;
    }

    /**
     * 取得hash表的阈值。
     * 
     * @return hash表的阈值
     */
    protected int getThreshold() {
        return threshold;
    }

    /** 代表hash表中的一个元素的类。 */
    protected final static class Entry {        
        protected int value;
        protected String key;
        protected Entry next;      
        protected Entry(String key, int value, Entry next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
        
        public int hashCode(){
        	return key.hashCode();
        }
	
		public String getKey() {
			// TODO Auto-generated method stub
			return key;
		}		
    }
    
    protected class HashIterator implements Iterator<java.util.Map.Entry<String, T>>{    	
    	
    	 Entry next;        // next entry to return
    	 Entry current;     // current entry
         int expectedModCount;  // for fast-fail
         int index;             // current slot

         HashIterator() {
             expectedModCount = count;
             Entry[] t = table;
             current = next = null;
             index = 0;
             if (t != null && size() > 0) { // advance to first entry
                 do {} while (index < t.length && (next = t[index++]) == null);
             }
         }

         public final boolean hasNext() {
             return next != null;
         }

         final Entry nextNode() {
        	 Entry[] t;
        	 Entry e = next;
             if (count != expectedModCount)
                 throw new ConcurrentModificationException();
             if (e == null)
                 throw new NoSuchElementException();
             if ((next = (current = e).next) == null && (t = table) != null) {
                 do {} while (index < t.length && (next = t[index++]) == null);
             }
             return e;
         }

         public final void remove() {
        	 Entry p = current;
             if (p == null)
                 throw new IllegalStateException();
             if (count != expectedModCount)
                 throw new ConcurrentModificationException();
             current = null;
             String key = p.key;
             p.value = 0;
             count--;
             expectedModCount = count;
         }
         
        
       

        @Override
        public java.util.Map.Entry<String, T> next()
        {
        	current = nextNode();
            //and return new object
            return new java.util.Map.Entry<String, T>()
            {

                @Override
                public String getKey()
                {
                    return current.key;
                }

                @Override
                public T getValue()
                {
                    int index = current.value;
                    return values.get(index);
                }

                @Override
                public T setValue(T value)
                {
                	int index = current.value;
                  
                	return values.set(index, value);
                }
            };
        }

       
    };
    
    /**
     * EntrySet class supports remove operations
     */
    private final class EntrySet extends AbstractSet<java.util.Map.Entry<String, T>>
    {      

        @Override
        public Iterator<java.util.Map.Entry<String, T>> iterator()
        {
            //find the first starting inded
            int START = 0;
            return new HashIterator();           
        }

        @Override
        public int size()
        {
            return count;
        }
        
    }
	
}
